1. Technical Field
This invention relates to information management, and more particularly to data base management systems.
2. Description of the Prior Art
A data base management system is a computer system for recording and maintaining data. In a relational data base management system, data is stored as rows in a table, with collections of tables being called data bases. One can manipulate (select, update, insert, or delete) data by issuing a request or command (called a query) to the data base. In a relational data base management system's data query and manipulation language, such as SQL, requests are nonprocedural (also referred to as navigational). That is, users simply specify what is wanted, rather than specifying how to accomplish it. The system's optimizer must determine the optimal way (or access path) to get the data for the user. One way to access data is to sequentially scan every row in a table for those rows which match the search criteria. This is known as a table scan, because the entire table is scanned in sequence from beginning to end.
Rows of data are stored on pages on physical storage devices, usually disk drives or files. Data is transferred between the physical storage and the computer system's processing unit page by page even though only a single row may be needed from a given page. The time it takes to transfer data between physical storage and the processing unit is many times greater than the time it takes to process the data in the processing unit. Furthermore, the time it takes to randomly access separate physical pages is as much as ten times longer than the time needed to sequentially access adjacent pages. To manipulate data in a relational data base, the rows must first be transferred from physical storage to the processing unit, then processed in the processing unit, and finally transferred back to physical storage. Because transferring takes so much longer than processing, the total time required to manipulate the data can be dramatically reduced if the number of transfers can be reduced.
Most relational data base systems maintain indexes for their tables. An index is a list stored separately from the rows and used to access the rows in a selected order. An index comprises many index entries, each containing a key value and an identifier of or pointer to one or more rows which contain that key value. Indexes are physically stored on index pages.
One method of storing an index's pages is as a B-tree, with a root page, intermediate pages depending from the root, and leaf pages depending from the intermediate pages at the lowest level of the tree. The term B-tree is short for "balanced tree", and refers to the balanced or roughly equal number of pages to which each such root or intermediate index page points. The B-tree's leaf pages contain the index entries. To scan a table's rows in the order specified by the index, the index's leaf pages are scanned sequentially and the index entries on each leaf page are used to access the rows in the index's order. This scan is called an index sequential scan, or index scan for short.
In the prior art, there are two types of index organizations: perfectly clustered and nonclustered. An index is perfectly clustered if, when scanning the index leaf pages sequentially, each data page is accessed only once. For this to occur the data rows, when accessed in index order, must be in the same sequence as the sequence in which they are stored in the data pages of physical storage. An index scan through a clustered index (also referred to as a clustered index scan) is fast because the number of data page accesses is minimized since there are no duplicate accesses to the same data page and because both the index leaf pages and the data pages can be accessed sequentially rather than at random.
An index is nonclustered if, when scanning the index leaf pages sequentially, the data pages are accessed back and forth at random. Index scans through nonclustered indexes (also referred to as nonclustered index scans) are extremely slow, because there is much thrashing back and forth between data pages as the index requires separate data pages to be randomly accessed and transferred into and out of the processing unit's main memory but only accesses one row from the many on each such page.
When an index's key is used as a search criterion in a query, that index can often provide an efficient access path for identifying these data rows which satisfy or match the search criteria. When a complex query having several criteria is presented, the data base system's optimizer often has a number of indexes available, each having a key the same as one of the search criteria. The optimizer must then select the best index with which to access the data rows.
The prior art teaches the desirability of clustered index scans as access paths for queries. However until now physical clustering of data has been considered an all-or-nothing proposition. Without taking into account the degree of clustering, the optimizer cannot discriminate between relatively more or less clustered indexes, and may choose a less efficient access path, resulting in unnecessary physical data page accesses.